/**
 * @author 雷明浩
 * @date 2025/6/27 9:53
 */
public class ReConstructBinaryTree {
    // 重建二叉树
    // http://nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private int index;
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        index = 0;
        return reConstructBinaryTreeChild(preOrder, vinOrder, 0, preOrder.length-1);
    }

    private TreeNode reConstructBinaryTreeChild(int[] preOrder, int[] vinOrder, int left, int right) {
        if (left > right) {
            return null;
        }
        int pivot = findIndex(vinOrder, left, right, preOrder[index]);
        TreeNode node = new TreeNode(preOrder[index++]);
        node.left = reConstructBinaryTreeChild(preOrder, vinOrder, left, pivot-1);
        node.right = reConstructBinaryTreeChild(preOrder, vinOrder, pivot+1, right);
        return node;
    }

    private int findIndex(int[] vinOrder, int left, int right, int target) {
        for (int i = left; i <= right; i++) {
            if (vinOrder[i] == target) {
                return i;
            }
        }
        return -1;
    }
}